{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Height of Binary Tree After Subtree Removal Queries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #array #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #数组 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: treeQueries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #移除子树后的二叉树高度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵 <strong>二叉树</strong> 的根节点 <code>root</code> ，树中有 <code>n</code> 个节点。每个节点都可以被分配一个从 <code>1</code> 到 <code>n</code> 且互不相同的值。另给你一个长度为 <code>m</code> 的数组 <code>queries</code> 。</p>\n",
    "\n",
    "<p>你必须在树上执行 <code>m</code> 个 <strong>独立</strong> 的查询，其中第 <code>i</code> 个查询你需要执行以下操作：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>从树中 <strong>移除</strong> 以 <code>queries[i]</code> 的值作为根节点的子树。题目所用测试用例保证 <code>queries[i]</code> <strong>不</strong> 等于根节点的值。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回一个长度为 <code>m</code> 的数组<em> </em><code>answer</code><em> </em>，其中<em> </em><code>answer[i]</code><em> </em>是执行第 <code>i</code> 个查询后树的高度。</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>查询之间是独立的，所以在每个查询执行后，树会回到其 <strong>初始</strong> 状态。</li>\n",
    "\t<li>树的高度是从根到树中某个节点的 <strong>最长简单路径中的边数</strong> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/09/07/binaryytreeedrawio-1.png\" style=\"width: 495px; height: 281px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,3,4,2,null,6,5,null,null,null,null,null,7], queries = [4]\n",
    "<strong>输出：</strong>[2]\n",
    "<strong>解释：</strong>上图展示了从树中移除以 4 为根节点的子树。\n",
    "树的高度是 2（路径为 1 -&gt; 3 -&gt; 2）。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/09/07/binaryytreeedrawio-2.png\" style=\"width: 301px; height: 284px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [5,8,9,2,1,3,7,4,6], queries = [3,2,4,8]\n",
    "<strong>输出：</strong>[3,2,3,2]\n",
    "<strong>解释：</strong>执行下述查询：\n",
    "- 移除以 3 为根节点的子树。树的高度变为 3（路径为 5 -&gt; 8 -&gt; 2 -&gt; 4）。\n",
    "- 移除以 2 为根节点的子树。树的高度变为 2（路径为 5 -&gt; 8 -&gt; 1）。\n",
    "- 移除以 4 为根节点的子树。树的高度变为 3（路径为 5 -&gt; 8 -&gt; 2 -&gt; 6）。\n",
    "- 移除以 8 为根节点的子树。树的高度变为 2（路径为 5 -&gt; 9 -&gt; 3）。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数目是 <code>n</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= n</code></li>\n",
    "\t<li>树中的所有值 <strong>互不相同</strong></li>\n",
    "\t<li><code>m == queries.length</code></li>\n",
    "\t<li><code>1 &lt;= m &lt;= min(n, 10<sup>4</sup>)</code></li>\n",
    "\t<li><code>1 &lt;= queries[i] &lt;= n</code></li>\n",
    "\t<li><code>queries[i] != root.val</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [height-of-binary-tree-after-subtree-removal-queries](https://leetcode.cn/problems/height-of-binary-tree-after-subtree-removal-queries/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [height-of-binary-tree-after-subtree-removal-queries](https://leetcode.cn/problems/height-of-binary-tree-after-subtree-removal-queries/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,4,2,null,6,5,null,null,null,null,null,7]\\n[4]', '[5,8,9,2,1,3,7,4,6]\\n[3,2,4,8]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.SIZE = 100_000\n",
    "        self.cache = [None] * (self.SIZE + 1)\n",
    "        self.ans = [0] * (self.SIZE + 1)\n",
    "\n",
    "    def dfs(self, root, depth):\n",
    "        if not root:\n",
    "            return depth - 1\n",
    "        if self.cache[root.val] is not None:\n",
    "            return self.cache[root.val]\n",
    "        self.cache[root.val] = max(self.dfs(root.left, depth + 1), self.dfs(root.right, depth + 1))\n",
    "        return self.cache[root.val]\n",
    "\n",
    "    def dfs2(self, root, depth, maxHeight):\n",
    "        if not root:\n",
    "            return\n",
    "        self.ans[root.val] = maxHeight\n",
    "\n",
    "        # 1. Handle right subtree\n",
    "        lv = self.dfs(root.left, depth + 1) if root.left else depth\n",
    "        self.dfs2(root.right, depth + 1, max(maxHeight, lv))\n",
    "\n",
    "        # 2. Handle left subtree\n",
    "        rv = self.dfs(root.right, depth + 1) if root.right else depth\n",
    "        self.dfs2(root.left, depth + 1, max(maxHeight, rv))\n",
    "\n",
    "    def treeQueries(self, root, queries):\n",
    "        self.dfs(root, 0)\n",
    "        self.dfs2(root, 0, 0)\n",
    "        return [self.ans[q] for q in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "levels = [0] * 100000\r\n",
    "depth = [0] * 100000\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\r\n",
    "        m = 0\r\n",
    "        n = 0\r\n",
    "\r\n",
    "        def postOrder(lvl: int, node: TreeNode) -> int:\r\n",
    "            nonlocal m, n\r\n",
    "            if node is None:\r\n",
    "                return 0\r\n",
    "            n += 1\r\n",
    "            m = max(m, lvl + 1)\r\n",
    "            levels[node.val - 1] = lvl\r\n",
    "            depth[node.val - 1] = max(postOrder(lvl + 1, node.left), postOrder(lvl + 1, node.right)) + 1\r\n",
    "            return depth[node.val - 1]\r\n",
    "        \r\n",
    "        postOrder(0, root)\r\n",
    "        depInLev = [[-1, -1] for _ in range(m)]\r\n",
    "        for i in range(n):\r\n",
    "            lvl = levels[i]\r\n",
    "            if depInLev[lvl][0] == -1 or depth[depInLev[lvl][0]] < depth[i]:\r\n",
    "                depInLev[lvl][1] = depInLev[lvl][0]\r\n",
    "                depInLev[lvl][0] = i\r\n",
    "            elif depInLev[lvl][1] == -1 or depth[depInLev[lvl][1]] < depth[i]:\r\n",
    "                depInLev[lvl][1] = i\r\n",
    "        \r\n",
    "        def qry(i: int) -> int:\r\n",
    "            if depInLev[levels[i - 1]][0] != i - 1:\r\n",
    "                return depth[root.val - 1] - 1\r\n",
    "            return depth[root.val - 1] - depth[i - 1] + depth[depInLev[levels[i - 1]][1]] - 1\r\n",
    "        \r\n",
    "        return list(map(qry, queries))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "maxn = 100010\n",
    "dfn = [0] * maxn\n",
    "deep = [0] * maxn\n",
    "size = [0] * maxn\n",
    "maxl = [0] * maxn\n",
    "maxr = [0] * maxn\n",
    "dfncnt = 0\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        global dfncnt\n",
    "        dfncnt = 0\n",
    "        def f(x, k):\n",
    "            global dfncnt\n",
    "            dfncnt += 1\n",
    "            i = dfncnt\n",
    "            deep[i] = k\n",
    "            size[i] = 1\n",
    "            dfn[x.val] = i\n",
    "            if x.left:\n",
    "                f(x.left, k+1)\n",
    "                size[i] += size[dfn[x.left.val]]\n",
    "            if x.right:\n",
    "                f(x.right, k+1)\n",
    "                size[i] += size[dfn[x.right.val]]\n",
    "        f(root, 0)\n",
    "        for i in range(1, dfncnt+1):\n",
    "            maxl[i] = max(maxl[i-1], deep[i])\n",
    "        maxr[dfncnt+1] = 0\n",
    "        for i in range(dfncnt, 0, -1):\n",
    "            maxr[i] = max(maxr[i+1], deep[i])\n",
    "        n = len(queries)\n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            leftmax = maxl[dfn[queries[i]] - 1]\n",
    "            rightmax = maxr[dfn[queries[i]] + size[dfn[queries[i]]]]\n",
    "            ans[i] = max(leftmax, rightmax)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = collections.defaultdict(int)\n",
    "        height[None] = -1\n",
    "        def getHeight(node):\n",
    "            if not node:\n",
    "                return -1\n",
    "            left = getHeight(node.left)\n",
    "            right = getHeight(node.right)\n",
    "            curHeight = max(left, right) + 1\n",
    "            height[node] = curHeight\n",
    "            return curHeight\n",
    "        getHeight(root)\n",
    "        # print([(k.val,v) for k, v in height.items()])\n",
    "        n = len(height)\n",
    "        res = [0] * (n + 1)\n",
    "        # def dfs(node, depth, restHeight):\n",
    "        #     if not node:\n",
    "        #         return\n",
    "        #     res[node.val] = restHeight\n",
    "        #     depth += 1\n",
    "        #     dfs(node.left, depth, max(restHeight, depth+height[node.right]))\n",
    "        #     dfs(node.right, depth, max(restHeight, depth+height[node.left]))\n",
    "        def dfs(node, depth, restHeight):\n",
    "            depth += 1\n",
    "            if node.left:\n",
    "                res[node.left.val] = max(restHeight, depth+height[node.right])\n",
    "                dfs(node.left, depth, res[node.left.val])\n",
    "            if node.right:\n",
    "                res[node.right.val] = max(restHeight, depth+height[node.left])\n",
    "                dfs(node.right, depth, res[node.right.val])\n",
    "        res[root.val] = -1\n",
    "        dfs(root, 0, 0)\n",
    "        for i in range(len(queries)):\n",
    "            queries[i] = res[queries[i]]\n",
    "        \n",
    "        return queries\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.height = defaultdict(int)\n",
    "        self.res = []\n",
    "\n",
    "    def get_height(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        left = self.get_height(root.left)\n",
    "        right = self.get_height(root.right)\n",
    "        self.height[root] = max(left, right) + 1\n",
    "        return self.height[root]\n",
    "\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        self.get_height(root)\n",
    "        self.res = [0] * (len(self.height)+1)\n",
    "        self.traverse(root, -1, 0)\n",
    "        for index, value in enumerate(queries):\n",
    "            queries[index] = self.res[value]\n",
    "        return queries\n",
    "\n",
    "    def traverse(self, root, depth, res_h):\n",
    "        if not root:\n",
    "            return\n",
    "        self.res[root.val] = res_h\n",
    "        depth += 1\n",
    "        self.traverse(root.left, depth, max(self.res[root.val], depth + self.height[root.right]))\n",
    "        self.traverse(root.right, depth, max(self.res[root.val], depth + self.height[root.left]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = defaultdict(int)\n",
    "\n",
    "        def get_height(node:'TreeNode'):\n",
    "            if node is None:return 0\n",
    "            height[node] = 1 + max(get_height(node.left), get_height(node.right))\n",
    "            return height[node]\n",
    "        \n",
    "        get_height(root)\n",
    "\n",
    "        res = [0] * (len(height) + 1)\n",
    "\n",
    "        def dfs(node, depth, rest_h):\n",
    "            if node is None: return\n",
    "            \n",
    "            depth += 1\n",
    "            res[node.val] = rest_h\n",
    "            dfs(node.left, depth, max(rest_h, height[node.right] + depth))\n",
    "            dfs(node.right, depth, max(rest_h, height[node.left] + depth))\n",
    "        dfs(root, -1, 0)\n",
    "        print(res)\n",
    "        ans = []\n",
    "        for i , q in enumerate(queries):\n",
    "            queries[i] = res[q]\n",
    "        return queries\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        mp = defaultdict(int)\n",
    "        \n",
    "        def dfs1(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            mp[node] = 1 + max(dfs1(node.left), dfs1(node.right))\n",
    "            return mp[node]\n",
    "        dfs1(root)\n",
    "        n = len(mp)\n",
    "        res = [0]*(n+1)\n",
    "        def dfs2(node, h, rest_h):\n",
    "            if not node:\n",
    "                return \n",
    "            h +=1\n",
    "            res[node.val] = rest_h\n",
    "            dfs2(node.left,h,max(rest_h, mp[node.right]+h))\n",
    "            dfs2(node.right,h,max(rest_h, mp[node.left]+h))\n",
    "        dfs2(root,-1,0)\n",
    "        # print(res)\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            ans.append(res[q])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "\n",
    "        height = defaultdict(int) # 每棵子树的高度(最长路径节点树)\n",
    "        def getheight(node: Optional[TreeNode])-> int:\n",
    "            if node is None: return 0\n",
    "            height[node] = 1 + max(getheight(node.left), getheight(node.right))\n",
    "            return height[node]\n",
    "        getheight(root)\n",
    "\n",
    "        res = [0] * (len(height) + 1) # 每个节点的答案\n",
    "        def dfs(node: Optional[TreeNode], depth:int, rest_h: int)-> None:\n",
    "            if node is None: return\n",
    "            depth += 1 # 维护当前节点深度\n",
    "            res[node.val] = rest_h\n",
    "            dfs(node.left, depth, max(rest_h, depth + height[node.right]))\n",
    "            dfs(node.right, depth, max(rest_h, depth + height[node.left]))\n",
    "\n",
    "        dfs(root, -1, 0)\n",
    "        for i, q in enumerate(queries):\n",
    "            queries[i] = res[q]\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "\n",
    "        height = defaultdict(int)  # 每棵子树的高度\n",
    "\n",
    "        def get_height(node: Optional[TreeNode]) -> int:\n",
    "\n",
    "            if node is None: return 0\n",
    "\n",
    "            height[node] = 1 + max(get_height(node.left), get_height(node.right))\n",
    "\n",
    "            return height[node]\n",
    "\n",
    "        get_height(root)\n",
    "\n",
    "\n",
    "        res = [0] * (len(height) + 1)  # 每个节点的答案\n",
    "\n",
    "        def dfs(node: Optional[TreeNode], depth: int, rest_h: int) -> None:\n",
    "\n",
    "            if node is None: return\n",
    "\n",
    "            depth += 1\n",
    "\n",
    "            res[node.val] = rest_h\n",
    "\n",
    "            dfs(node.left, depth, max(rest_h, depth + height[node.right]))\n",
    "\n",
    "            dfs(node.right, depth, max(rest_h, depth + height[node.left]))\n",
    "\n",
    "        dfs(root, -1, 0)\n",
    "\n",
    "\n",
    "\n",
    "        for i, q in enumerate(queries):\n",
    "\n",
    "            queries[i] = res[q]\n",
    "\n",
    "        return queries\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = defaultdict(int)  # 每棵子树的高度\n",
    "        def get_height(node: Optional[TreeNode]) -> int:\n",
    "            if node is None: return 0\n",
    "            height[node] = 1 + max(get_height(node.left), get_height(node.right))\n",
    "            return height[node]\n",
    "        get_height(root)\n",
    "\n",
    "        res = [0] * (len(height) + 1)  # 每个节点的答案\n",
    "        def dfs(node: Optional[TreeNode], depth: int, rest_h: int) -> None:\n",
    "            if node is None: return\n",
    "            depth += 1\n",
    "            res[node.val] = rest_h\n",
    "            dfs(node.left, depth, max(rest_h, depth + height[node.right]))\n",
    "            dfs(node.right, depth, max(rest_h, depth + height[node.left]))\n",
    "        dfs(root, -1, 0)\n",
    "\n",
    "        for i, q in enumerate(queries):\n",
    "            queries[i] = res[q]\n",
    "        return queries\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = defaultdict(int)  # 每棵子树的高度\n",
    "        def get_height(node: Optional[TreeNode]) -> int:\n",
    "            if node is None: return 0\n",
    "            height[node] = 1 + max(get_height(node.left), get_height(node.right))\n",
    "            return height[node]\n",
    "        get_height(root)\n",
    "\n",
    "        res = [0] * (len(height) + 1)  # 每个节点的答案\n",
    "        def dfs(node: Optional[TreeNode], depth: int, rest_h: int) -> None:\n",
    "            if node is None: return\n",
    "            res[node.val] = rest_h\n",
    "            # rest_h means height , compare with path from root to this node # seg, then turn to the right child # seg\n",
    "            dfs(node.left, depth + 1, max(rest_h, depth + height[node.right]))\n",
    "            dfs(node.right, depth + 1, max(rest_h, depth + height[node.left]))\n",
    "        dfs(root, 0, 0)\n",
    "\n",
    "        for i, q in enumerate(queries):\n",
    "            queries[i] = res[q]\n",
    "        return queries\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = defaultdict(int)\n",
    "        def get_height(node):\n",
    "            if not node: return 0\n",
    "            height[node] = 1 + max(get_height(node.left), get_height(node.right))\n",
    "            return height[node]\n",
    "        get_height(root)\n",
    "\n",
    "        res = [0] * (len(height) + 1)\n",
    "        def dfs(node, depth, rest_h):\n",
    "            if not node: return \n",
    "            depth += 1\n",
    "            res[node.val] = rest_h\n",
    "            dfs(node.left, depth, max(rest_h, depth + height[node.right]))\n",
    "            dfs(node.right, depth, max(rest_h, depth + height[node.left]))\n",
    "        dfs(root, -1, 0)\n",
    "        for i, q in enumerate(queries):\n",
    "            queries[i] = res[q]\n",
    "        return queries\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = defaultdict(int)  # 每棵子树的高度\n",
    "        def get_height(node: Optional[TreeNode]) -> int:\n",
    "            if node is None: return 0\n",
    "            height[node] = 1 + max(get_height(node.left), get_height(node.right))\n",
    "            return height[node]\n",
    "        get_height(root)\n",
    "\n",
    "        res = [0] * (len(height) + 1)  # 每个节点的答案\n",
    "        def dfs(node: Optional[TreeNode], depth: int, rest_h: int) -> None:\n",
    "            if node is None: return\n",
    "            depth += 1\n",
    "            res[node.val] = rest_h\n",
    "            dfs(node.left, depth, max(rest_h, depth + height[node.right]))\n",
    "            dfs(node.right, depth, max(rest_h, depth + height[node.left]))\n",
    "        dfs(root, -1, 0)\n",
    "\n",
    "        for i, q in enumerate(queries):\n",
    "            queries[i] = res[q]\n",
    "        return queries\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        # 求每个节点的最大高度\n",
    "        h = defaultdict(int)\n",
    "        def get_heigh(node):\n",
    "            if not node:return 0\n",
    "            h[node] = max(get_heigh(node.left),get_heigh(node.right)) + 1\n",
    "            return h[node]\n",
    "        get_heigh(root)\n",
    "        # 计算删除node后，树的最大边数\n",
    "        res = [0]*(len(h)+1)\n",
    "        def dfs(node,depth,l_h):\n",
    "            if node is None:return\n",
    "            res[node.val] = l_h\n",
    "            dfs(node.left,depth+1,max(l_h,1+depth+h[node.right]))\n",
    "            dfs(node.right,depth+1,max(l_h,1+depth+h[node.left]))\n",
    "        dfs(root,-1,0)\n",
    "        for i,v in enumerate(queries):\n",
    "            queries[i] = res[v]\n",
    "        return queries\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = {}\n",
    "        \n",
    "        def get_height(node: Optional[TreeNode]):\n",
    "            if node is None:\n",
    "                height[node] = 0\n",
    "                return 0\n",
    "            height[node] = 1 + max(get_height(node.left), get_height(node.right))\n",
    "            return height[node]\n",
    "        get_height(root)\n",
    "\n",
    "        res =   [0] * (len(height) + 1);\n",
    "\n",
    "        def dfs(node: Optional[TreeNode], depth: int, rest_h: int) -> None:\n",
    "            if node is None:\n",
    "                return\n",
    "            depth += 1\n",
    "            # to keep track of the maximum height encountered so far during the depth-first search (DFS) of the tree.\n",
    "            res[node.val] = rest_h\n",
    "            dfs(node.left, depth, max(rest_h, depth + height[node.right]))\n",
    "            dfs(node.right, depth, max(rest_h, depth + height[node.left]))\n",
    "        dfs(root, -1, 0)\n",
    "        for i,q in enumerate(queries):\n",
    "            queries[i] = res[q]\n",
    "        return queries\n",
    "\n",
    "\n",
    "\n",
    "class Solution2:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = defaultdict(int)\n",
    "        \n",
    "        def get_height(node: Optional[TreeNode]) -> int:\n",
    "            if node is None: \n",
    "                return 0\n",
    "            height[node] = 1 + max(get_height(node.left), get_height(node.right))\n",
    "            return height[node]\n",
    "        \n",
    "        get_height(root)\n",
    "        \n",
    "        res = [0] * (len(height) + 1)\n",
    "        \n",
    "        def dfs(node: Optional[TreeNode], depth: int, rest_h: int) -> None:\n",
    "            if node is None: \n",
    "                return\n",
    "            depth += 1\n",
    "            res[node.val] = rest_h\n",
    "            dfs(node.left, depth, max(rest_h, depth + height[node.right]))\n",
    "            dfs(node.right, depth, max(rest_h, depth + height[node.left]))\n",
    "        \n",
    "        dfs(root, -1, 0)\n",
    "        \n",
    "        for i, q in enumerate(queries):\n",
    "            queries[i] = res[q]\n",
    "        \n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = defaultdict(int)  # 每棵子树的高度\n",
    "        def get_height(node: Optional[TreeNode]) -> int:\n",
    "            if node is None: return 0\n",
    "            height[node] = 1 + max(get_height(node.left), get_height(node.right))\n",
    "            return height[node]\n",
    "        get_height(root)\n",
    "\n",
    "        res = [0] * (len(height) + 1)  # 每个节点的答案\n",
    "        def dfs(node: Optional[TreeNode], depth: int, rest_h: int) -> None:\n",
    "            if node is None: return\n",
    "            depth += 1\n",
    "            res[node.val] = rest_h\n",
    "            dfs(node.left, depth, max(rest_h, depth + height[node.right]))\n",
    "            dfs(node.right, depth, max(rest_h, depth + height[node.left]))\n",
    "        dfs(root, -1, 0)\n",
    "\n",
    "        for i, q in enumerate(queries):\n",
    "            queries[i] = res[q]\n",
    "        return queries\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = defaultdict(int)  # 每棵子树的高度\n",
    "        def get_height(node: Optional[TreeNode]) -> int:\n",
    "            if node is None: return 0\n",
    "            height[node] = 1 + max(get_height(node.left), get_height(node.right))\n",
    "            return height[node]\n",
    "        get_height(root)\n",
    "\n",
    "        res = [0] * (len(height) + 1)  # 每个节点的答案\n",
    "        def dfs(node: Optional[TreeNode], depth: int, rest_h: int) -> None:\n",
    "            if node is None: return\n",
    "            depth += 1\n",
    "            res[node.val] = rest_h\n",
    "            dfs(node.left, depth, max(rest_h, depth + height[node.right]))\n",
    "            dfs(node.right, depth, max(rest_h, depth + height[node.left]))\n",
    "        dfs(root, -1, 0)\n",
    "\n",
    "        for i, q in enumerate(queries):\n",
    "            queries[i] = res[q]\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = defaultdict(int)  # 每棵子树的高度\n",
    "        def get_height(node: Optional[TreeNode]) -> int:\n",
    "            if node is None: return 0\n",
    "            height[node] = 1 + max(get_height(node.left), get_height(node.right))\n",
    "            return height[node]\n",
    "        get_height(root)\n",
    "\n",
    "        res = [0] * (len(height) + 1)  # 每个节点的答案\n",
    "        def dfs(node: Optional[TreeNode], depth: int, rest_h: int) -> None:\n",
    "            if node is None: return\n",
    "            depth += 1\n",
    "            res[node.val] = rest_h\n",
    "            dfs(node.left, depth, max(rest_h, depth + height[node.right]))\n",
    "            dfs(node.right, depth, max(rest_h, depth + height[node.left]))\n",
    "        dfs(root, -1, 0)\n",
    "\n",
    "        for i, q in enumerate(queries):\n",
    "            queries[i] = res[q]\n",
    "        return queries\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = defaultdict(int)  # 每棵子树的高度\n",
    "        def get_height(node: Optional[TreeNode]) -> int:\n",
    "            if node is None: return 0\n",
    "            height[node] = 1 + max(get_height(node.left), get_height(node.right))\n",
    "            return height[node]\n",
    "        get_height(root)\n",
    "\n",
    "        res = [0] * (len(height) + 1)  # 每个节点的答案\n",
    "        def dfs(node: Optional[TreeNode], depth: int, rest_h: int) -> None:\n",
    "            if node is None: return\n",
    "            res[node.val] = rest_h\n",
    "            dfs(node.left, depth + 1, max(rest_h, depth + height[node.right]))\n",
    "            dfs(node.right, depth + 1, max(rest_h, depth + height[node.left]))\n",
    "        dfs(root, 0, 0)\n",
    "\n",
    "        for i, q in enumerate(queries):\n",
    "            queries[i] = res[q]\n",
    "        return queries\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = defaultdict(int)  # 每棵子树的高度\n",
    "        def get_height(node: Optional[TreeNode]) -> int:\n",
    "            if node is None: return 0\n",
    "            height[node] = 1 + max(get_height(node.left), get_height(node.right))\n",
    "            return height[node]\n",
    "        get_height(root)\n",
    "\n",
    "        res = [0] * (len(height) + 1)  # 每个节点的答案\n",
    "        def dfs(node: Optional[TreeNode], depth: int, rest_h: int) -> None:\n",
    "            if node is None: return\n",
    "            depth += 1\n",
    "            res[node.val] = rest_h\n",
    "            dfs(node.left, depth, max(rest_h, depth + height[node.right]))\n",
    "            dfs(node.right, depth, max(rest_h, depth + height[node.left]))\n",
    "        dfs(root, -1, 0)\n",
    "\n",
    "        for i, q in enumerate(queries):\n",
    "            queries[i] = res[q]\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = defaultdict(int)  # 每棵子树的高度\n",
    "        def get_height(node: Optional[TreeNode]) -> int:\n",
    "            if node is None: return 0\n",
    "            height[node] = 1 + max(get_height(node.left), get_height(node.right))\n",
    "            return height[node]\n",
    "        get_height(root)\n",
    "\n",
    "        res = [0] * (len(height) + 1)  # 每个节点的答案\n",
    "        def dfs(node: Optional[TreeNode], depth: int, rest_h: int) -> None:\n",
    "            if node is None: return\n",
    "            res[node.val] = rest_h\n",
    "            # rest_h means height , compare with path from root to this node # seg, then turn to the right child # seg\n",
    "            dfs(node.left, depth + 1, max(rest_h, depth + height[node.right]))\n",
    "            dfs(node.right, depth + 1, max(rest_h, depth + height[node.left]))\n",
    "        dfs(root, 0, 0)\n",
    "\n",
    "        for i, q in enumerate(queries):\n",
    "            queries[i] = res[q]\n",
    "        return queries\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        height = defaultdict(int)\n",
    "        def get_height(node):\n",
    "            if not node: return 0\n",
    "            height[node] = 1 + max(get_height(node.left), get_height(node.right))\n",
    "            return height[node]\n",
    "        get_height(root)\n",
    "        res = [0] * (len(height) + 1)\n",
    "        def dfs(node, depth, rest_h):\n",
    "            if not node:\n",
    "                return\n",
    "            depth += 1\n",
    "            res[node.val] = rest_h\n",
    "            dfs(node.left, depth, max(rest_h, depth+height[node.right]))\n",
    "            dfs(node.right, depth, max(rest_h, depth+height[node.left]))\n",
    "        dfs(root, -1, 0)\n",
    "        for i, q in enumerate(queries):\n",
    "            queries[i] = res[q]\n",
    "        return queries\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = defaultdict(int)  # 每棵子树的高度\n",
    "        def get_height(node: Optional[TreeNode]) -> int:\n",
    "            if node is None: return 0\n",
    "            height[node] = 1 + max(get_height(node.left), get_height(node.right))\n",
    "            return height[node]\n",
    "        get_height(root)\n",
    "\n",
    "        res = [0] * (len(height) + 1)  # 每个节点的答案\n",
    "        def dfs(node: Optional[TreeNode], depth: int, rest_h: int) -> None:\n",
    "            if node is None: return\n",
    "            depth += 1\n",
    "            res[node.val] = rest_h\n",
    "            dfs(node.left, depth, max(rest_h, depth + height[node.right]))\n",
    "            dfs(node.right, depth, max(rest_h, depth + height[node.left]))\n",
    "        dfs(root, -1, 0)\n",
    "\n",
    "        for i, q in enumerate(queries):\n",
    "            queries[i] = res[q]\n",
    "        return queries\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = {}\n",
    "        \n",
    "        def get_height(node: Optional[TreeNode]):\n",
    "            if node is None:\n",
    "                height[node] = 0\n",
    "                return 0\n",
    "            height[node] = 1 + max(get_height(node.left), get_height(node.right))\n",
    "            return height[node]\n",
    "        get_height(root)\n",
    "\n",
    "        # the res list is used to store the intermediate results of the height of the tree after removing the subtree rooted at each node, and it is then used to update the queries list with the final results.\n",
    "        res =   [0] * (len(height) + 1);\n",
    "\n",
    "        def dfs(node: Optional[TreeNode], depth: int, rest_h: int) -> None:\n",
    "            if node is None:\n",
    "                return\n",
    "            depth += 1\n",
    "            # to keep track of the maximum height encountered so far during the depth-first search (DFS) of the tree.\n",
    "            res[node.val] = rest_h\n",
    "            dfs(node.left, depth, max(rest_h, depth + height[node.right]))\n",
    "            dfs(node.right, depth, max(rest_h, depth + height[node.left]))\n",
    "        dfs(root, -1, 0)\n",
    "        for i,q in enumerate(queries):\n",
    "            queries[i] = res[q]\n",
    "        return queries\n",
    "\n",
    "\n",
    "\n",
    "class Solution2:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = defaultdict(int)\n",
    "        \n",
    "        def get_height(node: Optional[TreeNode]) -> int:\n",
    "            if node is None: \n",
    "                return 0\n",
    "            height[node] = 1 + max(get_height(node.left), get_height(node.right))\n",
    "            return height[node]\n",
    "        \n",
    "        get_height(root)\n",
    "        \n",
    "        res = [0] * (len(height) + 1)\n",
    "        \n",
    "        def dfs(node: Optional[TreeNode], depth: int, rest_h: int) -> None:\n",
    "            if node is None: \n",
    "                return\n",
    "            depth += 1\n",
    "            res[node.val] = rest_h\n",
    "            dfs(node.left, depth, max(rest_h, depth + height[node.right]))\n",
    "            dfs(node.right, depth, max(rest_h, depth + height[node.left]))\n",
    "        \n",
    "        dfs(root, -1, 0)\n",
    "        \n",
    "        for i, q in enumerate(queries):\n",
    "            queries[i] = res[q]\n",
    "        \n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = defaultdict(int)\n",
    "        def get_h(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            cur = max(get_h(root.left), get_h(root.right)) + 1\n",
    "            height[root] = cur\n",
    "            return cur\n",
    "        get_h(root)\n",
    "\n",
    "        res = [0] * (len(height) + 1)\n",
    "        ans = []\n",
    "        def dfs(root, depth, res_h):\n",
    "            if not root:\n",
    "                return\n",
    "            res[root.val] = res_h\n",
    "            depth += 1\n",
    "            dfs(root.left, depth, max(res_h, depth + height[root.right]))\n",
    "            dfs(root.right, depth, max(res_h, depth + height[root.left]))\n",
    "        dfs(root, -1, 0)\n",
    "        print(res)\n",
    "        for x in queries:\n",
    "            ans.append(res[x])\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        d = defaultdict(int)\n",
    "        def dfs_height(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            h = max(dfs_height(node.left), dfs_height(node.right)) + 1\n",
    "            d[node] = h \n",
    "            return h \n",
    "        dfs_height(root)\n",
    "        \n",
    "        res = [0] * (len(d) + 1)\n",
    "        def dfs(node, height, rest_h):\n",
    "            if not node:\n",
    "                return \n",
    "            height += 1\n",
    "            res[node.val] = rest_h\n",
    "            dfs(node.left, height, max(rest_h, height + d[node.right]))\n",
    "            dfs(node.right, height, max(rest_h, height + d[node.left]))\n",
    "        dfs(root, -1, 0)\n",
    "\n",
    "        for i, q in enumerate(queries):\n",
    "            queries[i] = res[q]\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = defaultdict(int)\n",
    "        def getDepth(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            left = getDepth(node.left)\n",
    "            right = getDepth(node.right)\n",
    "            height[node] = max(left, right) + 1\n",
    "            return height[node]\n",
    "        getDepth(root)\n",
    "        res = [0] * (len(height) + 1)\n",
    "        print(height.values())\n",
    "        def dfs(node, depth, restHeight):\n",
    "            if not node:\n",
    "                return None\n",
    "            res[node.val] = restHeight\n",
    "            depth += 1\n",
    "            dfs(node.left, depth, max(restHeight, depth+height[node.right]))\n",
    "            dfs(node.right, depth, max(restHeight, depth+height[node.left]))\n",
    "        dfs(root, -1, 0)\n",
    "        for i, target in enumerate(queries):\n",
    "            queries[i] = res[target]\n",
    "\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        # dfs might go to null node, therefore use defaultdict\n",
    "        height = defaultdict(int)  # 每棵子树的高度\n",
    "        def get_height(node: Optional[TreeNode]) -> int:\n",
    "            # null node set to zero\n",
    "            # return # of nodes, leaf node is 1\n",
    "            # if we define leaf node as zero, it will get conflict with null node because null node is also zero\n",
    "            if node is None: return 0\n",
    "            height[node] = 1 + max(get_height(node.left), get_height(node.right))\n",
    "            return height[node]\n",
    "        get_height(root)\n",
    "\n",
    "        res = [0] * (len(height) + 1)  # 每个节点的答案\n",
    "        def dfs(node: Optional[TreeNode], depth: int, rest_h: int) -> None:\n",
    "            if node is None: return\n",
    "            res[node.val] = rest_h\n",
    "            # rest_h means height , compare with path from root to this node # seg, then turn to the right child # seg\n",
    "            dfs(node.left, depth + 1, max(rest_h, depth + height[node.right]))\n",
    "            dfs(node.right, depth + 1, max(rest_h, depth + height[node.left]))\n",
    "        dfs(root, 0, 0)\n",
    "\n",
    "        for i, q in enumerate(queries):\n",
    "            queries[i] = res[q]\n",
    "        return queries\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = defaultdict(int)  # 每棵子树的高度\n",
    "        def get_height(node: Optional[TreeNode]) -> int:\n",
    "            if node is None: return 0\n",
    "            height[node] = 1 + max(get_height(node.left), get_height(node.right))\n",
    "            return height[node]\n",
    "        get_height(root)\n",
    "\n",
    "        res = [0] * (len(height) + 1)  # 每个节点的答案\n",
    "        def dfs(node: Optional[TreeNode], depth: int, rest_h: int) -> None:\n",
    "            if node is None: return\n",
    "            res[node.val] = rest_h\n",
    "            # rest_h means height , compare with path from root to this node # seg, then turn to the right child # seg\n",
    "            dfs(node.left, depth + 1, max(rest_h, depth + height[node.right]))\n",
    "            dfs(node.right, depth + 1, max(rest_h, depth + height[node.left]))\n",
    "        dfs(root, 0, 0)\n",
    "\n",
    "        for i, q in enumerate(queries):\n",
    "            queries[i] = res[q]\n",
    "        return queries\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = defaultdict(int)  # 每棵子树的高度\n",
    "        def get_height(node: Optional[TreeNode]) -> int:\n",
    "            if node is None: return 0\n",
    "            height[node] = 1 + max(get_height(node.left), get_height(node.right))\n",
    "            return height[node]\n",
    "        get_height(root)\n",
    "\n",
    "        res = [0] * (len(height) + 1)  # 每个节点的答案\n",
    "        def dfs(node: Optional[TreeNode], depth: int, rest_h: int) -> None:\n",
    "            if node is None: return\n",
    "            depth += 1\n",
    "            res[node.val] = rest_h\n",
    "            dfs(node.left, depth, max(rest_h, depth + height[node.right]))\n",
    "            dfs(node.right, depth, max(rest_h, depth + height[node.left]))\n",
    "        dfs(root, -1, 0)\n",
    "\n",
    "        for i, q in enumerate(queries):\n",
    "            queries[i] = res[q]\n",
    "        return queries\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = {}\n",
    "        def dfs(root):\n",
    "            ret = 0\n",
    "            if root.left and root.right:\n",
    "                ret = 1 + max(dfs(root.left), dfs(root.right))\n",
    "            elif root.left:\n",
    "                ret = 1 + dfs(root.left)\n",
    "            elif root.right:\n",
    "                ret = 1 + dfs(root.right)\n",
    "            height[root.val] = ret\n",
    "            return ret\n",
    "        dfs(root)\n",
    "        node_level = {}\n",
    "        level_node = defaultdict(lambda: [-1, -1])\n",
    "        cur_level = 0\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                u = q.popleft()\n",
    "                val = u.val\n",
    "                node_level[val] = cur_level\n",
    "                if height[val] > level_node[cur_level][0]:\n",
    "                    level_node[cur_level][1] = level_node[cur_level][0]\n",
    "                    level_node[cur_level][0] = height[val]\n",
    "                elif height[val] > level_node[cur_level][1]:\n",
    "                    level_node[cur_level][1] = height[val]\n",
    "                if u.left: q.append(u.left)\n",
    "                if u.right: q.append(u.right)\n",
    "            cur_level += 1\n",
    "        ans = []\n",
    "        for i in queries:\n",
    "            if height[i] != level_node[node_level[i]][0]:\n",
    "                ans.append(level_node[node_level[i]][0] + node_level[i])\n",
    "            else:\n",
    "                ans.append(level_node[node_level[i]][1] + node_level[i])\n",
    "        return ans\n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = collections.defaultdict(int)\n",
    "        height[None] = -1\n",
    "        def getHeight(node):\n",
    "            if not node:\n",
    "                return -1\n",
    "            left = getHeight(node.left)\n",
    "            right = getHeight(node.right)\n",
    "            curHeight = max(left, right) + 1\n",
    "            height[node] = curHeight\n",
    "            return curHeight\n",
    "        getHeight(root)\n",
    "        # print([(k.val,v) for k, v in height.items()])\n",
    "        n = len(height)\n",
    "        res = [0] * (n + 1)\n",
    "        def dfs(node, depth, restHeight):\n",
    "            if not node:\n",
    "                return\n",
    "            res[node.val] = restHeight\n",
    "            depth += 1\n",
    "            dfs(node.left, depth, max(restHeight, depth+height[node.right]))\n",
    "            dfs(node.right, depth, max(restHeight, depth+height[node.left]))\n",
    "        dfs(root, 0, 0)\n",
    "        for i in range(len(queries)):\n",
    "            queries[i] = res[queries[i]]\n",
    "        \n",
    "        return queries\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        node_height = defaultdict(int)  # 节点与高度映射\n",
    "        level_nodes = defaultdict(list) # 层和该层的节点集映射\n",
    "        node_level = defaultdict(int)  # 节点和该节点所在层映射\n",
    "        \n",
    "        # dfs求每个节点的高度（后序遍历，自底向上）\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            l = dfs(root.left)\n",
    "            r = dfs(root.right)\n",
    "            h = max(l, r) + 1\n",
    "            node_height[root.val] = h\n",
    "            return h\n",
    "        dfs(root)\n",
    "\n",
    "        ans = []\n",
    "        rh = node_height[root.val]  # 根节点的高度\n",
    "        \n",
    "        # bfs求节点所在层，及每层的节点集\n",
    "        dq = deque()\n",
    "        l = 1\n",
    "        dq.append(root)\n",
    "        while dq:\n",
    "            n = len(dq)\n",
    "            for i in range(n):\n",
    "                cur = dq.popleft()\n",
    "                level_nodes[l].append(cur.val)\n",
    "                node_level[cur.val] = l\n",
    "                if cur.left:\n",
    "                    dq.append(cur.left)\n",
    "                if cur.right:\n",
    "                    dq.append(cur.right)\n",
    "            l += 1\n",
    "    \n",
    "        # print(node_height)\n",
    "        # print(level_nodes)\n",
    "        # print(node_level)\n",
    "        for i in range(len(queries)):\n",
    "            q = queries[i]\n",
    "            l = node_level[q]\n",
    "            h = node_height[q]\n",
    "            # 如果该节点所在层只有一个节点（没有兄弟节点）\n",
    "            if len(level_nodes[l]) == 1:\n",
    "                ans.append(rh - h - 1)\n",
    "            # 有兄弟节点\n",
    "            else:\n",
    "                max_h = 0  # 兄弟节点中的最大高度（不包括自己）\n",
    "                for node in level_nodes[l]:\n",
    "                    if node == q:\n",
    "                        continue\n",
    "                    max_h = max(max_h, node_height[node])\n",
    "                    # 兄弟节点中有节点高度不小于要删除的节点高度，\n",
    "                    # 删除节点后树的高度不变\n",
    "                    if max_h >= h:\n",
    "                        ans.append(rh - 1)\n",
    "                        break\n",
    "                # 要删除的节点是该层中高度最高的节点\n",
    "                if max_h < h:\n",
    "                    ans.append(rh - (h - max_h) - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeQueries(self, root, queries):\n",
    "        node_height = defaultdict(int)  # 节点与高度映射\n",
    "        level_nodes = defaultdict(list) # 层和该层的节点集映射\n",
    "        node_level = defaultdict(int)  # 节点和该节点所在层映射\n",
    "        \n",
    "        # dfs求每个节点的高度（后序遍历，自底向上）\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            l = dfs(root.left)\n",
    "            r = dfs(root.right)\n",
    "            h = max(l, r) + 1\n",
    "            node_height[root.val] = h\n",
    "            return h\n",
    "        dfs(root)\n",
    "\n",
    "        ans = []\n",
    "        rh = node_height[root.val]  # 根节点的高度\n",
    "        \n",
    "        # bfs求节点所在层，及每层的节点集\n",
    "        dq = deque()\n",
    "        l = 1\n",
    "        dq.append(root)\n",
    "        while dq:\n",
    "            n = len(dq)\n",
    "            for i in range(n):\n",
    "                cur = dq.popleft()\n",
    "                level_nodes[l].append(cur.val)\n",
    "                node_level[cur.val] = l\n",
    "                if cur.left:\n",
    "                    dq.append(cur.left)\n",
    "                if cur.right:\n",
    "                    dq.append(cur.right)\n",
    "            l += 1\n",
    "    \n",
    "        for i in range(len(queries)):\n",
    "            q = queries[i]\n",
    "            l = node_level[q]\n",
    "            h = node_height[q]\n",
    "            # 如果该节点所在层只有一个节点（没有兄弟节点）\n",
    "            if len(level_nodes[l]) == 1:\n",
    "                ans.append(rh - h - 1)\n",
    "            # 有兄弟节点\n",
    "            else:\n",
    "                max_h = 0  # 兄弟节点中的最大高度（不包括自己）\n",
    "                for node in level_nodes[l]:\n",
    "                    if node == q:\n",
    "                        continue\n",
    "                    max_h = max(max_h, node_height[node])\n",
    "                    # 兄弟节点中有节点高度不小于要删除的节点高度，\n",
    "                    # 删除节点后树的高度不变\n",
    "                    if max_h >= h:\n",
    "                        ans.append(rh - 1)\n",
    "                        break\n",
    "                # 要删除的节点是该层中高度最高的节点\n",
    "                if max_h < h:\n",
    "                    ans.append(rh - (h - max_h) - 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        def dfs(u, cur):\n",
    "            nonlocal depth\n",
    "            nonlocal cache\n",
    "            if u is None:\n",
    "                return -1\n",
    "            depth[u.val] = cur\n",
    "            bottom = max(dfs(u.left, cur + 1), dfs(u.right, cur + 1)) + 1\n",
    "            layer = cache[cur]\n",
    "            if layer[0][1] <= bottom:\n",
    "                layer[1] = layer[0]\n",
    "                layer[0] = (u.val, bottom)\n",
    "            elif layer[1][1] < bottom:\n",
    "                layer[1] = (u.val, bottom)\n",
    "            return bottom\n",
    "\n",
    "        depth = dict()\n",
    "        cache = defaultdict(lambda :[(0, -1), (0, -1)])  #val, bottom\n",
    "        dfs(root, 0)\n",
    "        # print(depth)\n",
    "        # print(cache)\n",
    "        ans = [cache[0][0][1]] * len(queries)\n",
    "        for i, v in enumerate(queries):\n",
    "            d = depth[v]\n",
    "            first, second = cache[d]\n",
    "            if first[0] == v:\n",
    "                ans[i] = d + second[1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        row, level = [], {}\n",
    "        \n",
    "        def dfs(head, lv):\n",
    "            if not head:\n",
    "                return 0\n",
    "\n",
    "            level[head.val] = lv\n",
    "            if len(row) <= lv:\n",
    "                row.append([])\n",
    "\n",
    "            l, r = dfs(head.left, lv+1), dfs(head.right, lv+1)\n",
    "            h = max(l, r) + 1\n",
    "\n",
    "            bisect.insort_left(row[lv], (h, head.val))\n",
    "            return h\n",
    "\n",
    "        maxh = dfs(root, 0)\n",
    "        #print(maxh, row)\n",
    "\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            lv = level[q]\n",
    "            #print('lv',q,lv,row[lv])\n",
    "            if row[lv][-1][1] != q:\n",
    "                res.append(maxh-1)\n",
    "            elif len(row[lv]) == 1:\n",
    "                res.append(lv-1)\n",
    "            else:\n",
    "                res.append(lv+row[lv][-2][0]-1)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.height = defaultdict(int)\n",
    "        self.rem_height = {}\n",
    "\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        self.post_traversal(root)\n",
    "        self.pre_traversal(root, 0, 0)\n",
    "        return [self.rem_height[val] for val in queries]\n",
    "\n",
    "    def post_traversal(self, node) -> int:\n",
    "        if node is None:\n",
    "            return 0\n",
    "\n",
    "        left = self.post_traversal(node.left)\n",
    "        right = self.post_traversal(node.right)\n",
    "        res = max(left, right) + 1\n",
    "        self.height[node] = res\n",
    "        return res\n",
    "\n",
    "    def pre_traversal(self, node, rem_h, level):\n",
    "        if node is None:\n",
    "            return\n",
    "\n",
    "        self.rem_height[node.val] = rem_h\n",
    "\n",
    "        # remainer height is max between height after removing parent, and height after removing left node\n",
    "        if node.left:\n",
    "            self.pre_traversal(node.left, max(rem_h, level + self.height[node.right]), level + 1)\n",
    "        if node.right:\n",
    "            self.pre_traversal(node.right, max(rem_h, level + self.height[node.left]), level + 1)\n",
    "\n",
    "        return\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        def getHeight(node,heights):\n",
    "            if not node:\n",
    "                return 0\n",
    "            if not node.left and not node.right: \n",
    "                heights[node.val] = 1\n",
    "                return 1\n",
    "            heights[node.val] = 1+max(getHeight(node.left,heights),getHeight(node.right,heights))\n",
    "            return heights[node.val]\n",
    "\n",
    "        def dfs(node,heights,depth,h,res):\n",
    "            if not node:\n",
    "                return\n",
    "            res[node.val] = h\n",
    "            depth += 1\n",
    "            if node.right:\n",
    "                dfs(node.left,heights,depth,max(depth+heights[node.right.val],h),res)\n",
    "            else:\n",
    "                dfs(node.left,heights,depth,max(depth,h),res)\n",
    "            if node.left:\n",
    "                dfs(node.right,heights,depth,max(depth+heights[node.left.val],h),res)\n",
    "            else:\n",
    "                dfs(node.right,heights,depth,max(depth,h),res)\n",
    "        heights = {}\n",
    "        getHeight(root,heights)\n",
    "        #print(heights)\n",
    "        res = {}\n",
    "        dfs(root,heights,-1,0,res)\n",
    "        #print(res)\n",
    "        rr = []\n",
    "        for q in queries:\n",
    "            rr.append(res[q])\n",
    "        return rr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        d = defaultdict(lambda: 0)\n",
    "        def dfs1(node = root):\n",
    "            if node is None: return 0\n",
    "            d[node] = 1 + max(dfs1(node.left),dfs1(node.right))\n",
    "            return d[node]\n",
    "        dfs1()\n",
    "        dd = {}\n",
    "        def dfs2(node = root,h = -1,mx = 0):\n",
    "            if node is None: return \n",
    "            h += 1\n",
    "            dd[node.val] = mx\n",
    "            dfs2(node.left,h,max(mx,d[node.right]+h))\n",
    "            dfs2(node.right,h,max(mx,d[node.left]+h))\n",
    "        dfs2()\n",
    "        return [dd[i] for i in queries]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.height = {}\n",
    "        self.rem_height = {}\n",
    "\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        self.post_traversal(root)\n",
    "        self.pre_traversal(root, 0, 0)\n",
    "        return [self.rem_height[val] for val in queries]\n",
    "\n",
    "    def post_traversal(self, node) -> int:\n",
    "        if node is None:\n",
    "            return 0\n",
    "\n",
    "        left = self.post_traversal(node.left)\n",
    "        right = self.post_traversal(node.right)\n",
    "        res = max(left, right) + 1\n",
    "        self.height[node] = res\n",
    "        return res\n",
    "\n",
    "    def pre_traversal(self, node, rem_h, level):\n",
    "        if node is None:\n",
    "            return\n",
    "\n",
    "        self.rem_height[node.val] = rem_h\n",
    "\n",
    "        # remainer height is max between height after removing parent, and height after removing left node\n",
    "        if node.left:\n",
    "            self.pre_traversal(node.left, max(rem_h, level + self.height.get(node.right, 0)), level + 1)\n",
    "        if node.right:\n",
    "            self.pre_traversal(node.right, max(rem_h, level + self.height.get(node.left, 0)), level + 1)\n",
    "\n",
    "        return\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = defaultdict(int)\n",
    "        def dfs(node, level):\n",
    "            if node is None:\n",
    "                return 0\n",
    "            lh = dfs(node.left, level + 1)\n",
    "            rh = dfs(node.right, level + 1)\n",
    "            height[node] = max(lh, rh) + 1\n",
    "            return height[node]\n",
    "        dfs(root, 0)\n",
    "        # print(child_height)\n",
    "        rm_height = dict()\n",
    "        def dfs2(node, depth, rest_h):\n",
    "            if node is None:\n",
    "                return\n",
    "            rm_height[node.val] = rest_h\n",
    "            dfs2(node.left, depth + 1, max(rest_h, depth + height[node.right]))\n",
    "            dfs2(node.right, depth + 1, max(rest_h, depth + height[node.left]))\n",
    "        dfs2(root, 0, 0)\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            ans.append(rm_height[q])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = defaultdict(int)\n",
    "        def dfs(i):\n",
    "            if not i: return 0\n",
    "            height[i] = 1 + max(dfs(i.left), dfs(i.right))\n",
    "            return height[i]\n",
    "        dfs(root)\n",
    "        res = defaultdict(int)\n",
    "        def dfs2(u, dep, ret):\n",
    "            if not u: return\n",
    "            dep += 1\n",
    "            res[u.val] = ret\n",
    "            dfs2(u.left, dep, max(ret, dep + height[u.right]))\n",
    "            dfs2(u.right, dep, max(ret, dep + height[u.left]))\n",
    "        dfs2(root, -1, 0)\n",
    "\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            ans.append(res[q])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DFS:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def gen_bfs_order_iteration(dct, root=0):\n",
    "        # 模板：生成深搜序即 dfs 序以及对应子树编号区间\n",
    "        n = len(dct)\n",
    "        for i in range(n):\n",
    "            dct[i].sort(reverse=True)  # 按照子节点编号从小到大进行遍历\n",
    "        order = 0\n",
    "        start = [-1] * n  # 每个原始节点的dfs序号开始点也是node_to_order\n",
    "        end = [-1]*n  # 每个原始节点的dfs序号结束点\n",
    "        parent = [-1]*n  # 每个原始节点的父节点\n",
    "        stack = [[root, -1]]\n",
    "        depth = [0]*n  # 每个原始节点的深度\n",
    "        order_to_node = [-1]*n  # 每个dfs序号对应的原始节点编号\n",
    "        while stack:\n",
    "            i, fa = stack.pop()\n",
    "            if i >= 0:\n",
    "                start[i] = order\n",
    "                order_to_node[order] = i\n",
    "                end[i] = order\n",
    "                order += 1\n",
    "                stack.append([~i, fa])\n",
    "                for j in dct[i]:\n",
    "                    if j != fa:  # 注意访问顺序可以进行调整，比如字典序正序逆序\n",
    "                        parent[j] = i\n",
    "                        depth[j] = depth[i] + 1\n",
    "                        stack.append([j, i])\n",
    "            else:\n",
    "                i = ~i\n",
    "                if parent[i] != -1:\n",
    "                    end[parent[i]] = end[i]\n",
    "\n",
    "        return start, end, [depth[x] for x in order_to_node]\n",
    "    \n",
    "    \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        \n",
    "        dct = defaultdict(list)\n",
    "        n = 0\n",
    "        \n",
    "        def dfs(node):\n",
    "            nonlocal n\n",
    "            if not node:\n",
    "                return \n",
    "            x = node.val - 1\n",
    "            if  x+1>n:\n",
    "                n = x+1\n",
    "            if node.left:\n",
    "                dct[x].append(node.left.val-1)\n",
    "                dfs(node.left)\n",
    "            if node.right:\n",
    "                dct[x].append(node.right.val - 1)\n",
    "                dfs(node.right)\n",
    "            return \n",
    "        dfs(root)\n",
    "        edge = [dct[i] for i in range(n)]\n",
    "        r = root.val - 1\n",
    "        start, end, depth = DFS().gen_bfs_order_iteration(edge, r)\n",
    "        \n",
    "        \n",
    "        pre = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            a, b = pre[i], depth[i]\n",
    "            pre[i+1] = a if a > b else b\n",
    "            \n",
    "        post =[0]*(n+1)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            a, b = post[i+1], depth[i]\n",
    "            post[i] = a if a > b else b\n",
    "            \n",
    "   \n",
    "        ans = []\n",
    "        for i in queries:\n",
    "            i -= 1\n",
    "            s, e = start[i], end[i]\n",
    "        \n",
    "            a = pre[s]\n",
    "            b = post[e+1]\n",
    "            ans.append(a if a > b else b)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "from typing import Optional, List\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "from typing import Optional, List\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param root:\n",
    "        :param queries:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = defaultdict(int)\n",
    "\n",
    "        def get_h(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            ret = max(get_h(node.left), get_h(node.right)) + 1\n",
    "            m1[node] = ret\n",
    "            return ret\n",
    "\n",
    "        get_h(root)\n",
    "\n",
    "        m2 = defaultdict(int)\n",
    "\n",
    "        def iter_h(node, depth, restH):\n",
    "            if not node:\n",
    "                return\n",
    "            m2[node.val] = restH\n",
    "            depth += 1\n",
    "            iter_h(node.left, depth, max(restH, depth+m1[node.right]))\n",
    "            iter_h(node.right, depth, max(restH, depth+m1[node.left]))\n",
    "\n",
    "        iter_h(root, -1, 0)\n",
    "\n",
    "        return [m2[node] for node in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = defaultdict(int)\n",
    "        def dfs(i):\n",
    "            if not i: return 0\n",
    "            height[i] = 1 + max(dfs(i.left), dfs(i.right))\n",
    "            return height[i]\n",
    "        #print(height)\n",
    "        dfs(root)\n",
    "        res = defaultdict(int)\n",
    "        def dfs2(u, dep, ret):\n",
    "            if not u: return\n",
    "            dep += 1\n",
    "            #print(u.val, dep, ret)\n",
    "            res[u.val] = ret\n",
    "            dfs2(u.left, dep, max(ret, dep + height[u.right]))\n",
    "            dfs2(u.right, dep, max(ret, dep + height[u.left]))\n",
    "        dfs2(root, -1, 0)\n",
    "\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            ans.append(res[q])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "\n",
    "        heights = defaultdict(int)\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:return 0\n",
    "            heights[node] = max(dfs(node.left) , dfs(node.right)) + 1\n",
    "            return heights[node]\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "        res = defaultdict(int)\n",
    "\n",
    "        def dfs(node,deep,val):\n",
    "            if not node:return\n",
    "            res[node.val] = val\n",
    "            deep += 1\n",
    "            dfs(node.left,deep,max(val,deep+heights[node.right]))\n",
    "            dfs(node.right,deep,max(val,deep+heights[node.left]))\n",
    "\n",
    "        dfs(root,-1,0)\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            ans.append(res[q])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "from copy import deepcopy\n",
    "\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = defaultdict(int)\n",
    "        # from button to top\n",
    "        def findHeight(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            height[node] = max(findHeight(node.left), findHeight(node.right)) + 1\n",
    "            return height[node]\n",
    "        findHeight(root)\n",
    "\n",
    "        height_wo_node = defaultdict(int)\n",
    "        def dfs(node, depth, rest_h):\n",
    "            if not node:\n",
    "                return\n",
    "            depth += 1\n",
    "            height_wo_node[node.val] = rest_h\n",
    "            dfs(node.left, depth, max(rest_h, depth + height[node.right]))\n",
    "            dfs(node.right, depth, max(rest_h, depth + height[node.left]))\n",
    "        dfs(root, 0, 0)\n",
    "\n",
    "        res = [height_wo_node[n]-1 for n in queries]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height, depth = dict(), dict()\n",
    "        peer = defaultdict(lambda: [0, 0])\n",
    "        def dfs(node: TreeNode, d=0):\n",
    "            if node is None: return 0\n",
    "            depth[node.val] = d\n",
    "            height[node.val] = t = 1 + max(dfs(node.left, d + 1), dfs(node.right, d + 1))\n",
    "            if t > peer[d][0]: t, peer[d][0] = peer[d][0], t\n",
    "            if t > peer[d][1]: peer[d][1] = t\n",
    "            return height[node.val]\n",
    "            \n",
    "        dfs(root)\n",
    "        return [height[root.val] - 1 - (0 if height[u] != peer[depth[u]][0] else height[u] - peer[depth[u]][1]) for u in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        self.dfn = 0\n",
    "        in_, out = {}, {}\n",
    "        hs = [-1]\n",
    "        \n",
    "        def dfs(rt, h):\n",
    "            if not rt:\n",
    "                return\n",
    "            self.dfn += 1\n",
    "            hs.append(h)\n",
    "            in_[rt.val] = self.dfn\n",
    "            dfs(rt.left, h + 1), dfs(rt.right, h + 1)\n",
    "            out[rt.val] = self.dfn\n",
    "\n",
    "        dfs(root, 0)\n",
    "        hs.append(-1)\n",
    "        n = len(hs) - 2\n",
    "        leftMax, rightMax = [0] * (n + 2), [0] * (n + 2)\n",
    "        for i in range(1, n + 1):\n",
    "            leftMax[i] = max(leftMax[i - 1], hs[i])\n",
    "            rightMax[n + 1 - i] = max(rightMax[n + 2 - i], hs[n + 1 - i])\n",
    "        return [max(leftMax[in_[q] - 1], rightMax[out[q] + 1]) for q in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        height = dict()\n",
    "        child_height = dict()\n",
    "        def dfs(node, level):\n",
    "            if node is None:\n",
    "                return -1\n",
    "            height[node.val] = level\n",
    "            lh = dfs(node.left, level + 1)\n",
    "            rh = dfs(node.right, level + 1)\n",
    "            child_height[node.val] = max(height[node.val], lh, rh)\n",
    "            return child_height[node.val]\n",
    "        dfs(root, 0)\n",
    "        # print(child_height)\n",
    "        rm_height = dict()\n",
    "        def dfs2(node, other_h):\n",
    "            if node is None:\n",
    "                return\n",
    "            rm_height[node.val] = max(other_h, height[node.val] - 1)\n",
    "            if node.left is not None:\n",
    "                h = max(other_h, child_height[node.right.val] if node.right is not None else 0)\n",
    "                dfs2(node.left, h)\n",
    "            if node.right is not None:\n",
    "                h = max(other_h, child_height[node.left.val] if node.left is not None else 0)\n",
    "                dfs2(node.right, h)\n",
    "        dfs2(root, 0)\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            ans.append(rm_height[q])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        left = {}\n",
    "        right = {}\n",
    "        depth = {}\n",
    "        self.idx = - 1 \n",
    "        def dfs(node, d):\n",
    "            if not node:\n",
    "                return \n",
    "            self.idx += 1 \n",
    "            left[node.val] = self.idx \n",
    "            depth[self.idx] = d \n",
    "            dfs(node.left, d + 1)\n",
    "            dfs(node.right, d + 1)\n",
    "            right[node.val] = self.idx \n",
    "        dfs(root, 0)\n",
    "        n = len(depth)\n",
    "        pre = [0] * (self.idx + 1)\n",
    "        post = [0] * (self.idx + 1)\n",
    "        for i in range(self.idx + 1):\n",
    "            pre[i] = max(pre[i - 1] if i > 0 else 0, depth[i])\n",
    "            post[n - i - 1] = max(post[n - i] if i > 0 else 0, depth[n - i - 1])\n",
    "        \n",
    "        res = []\n",
    "        for rt in queries:\n",
    "            res.append(max(pre[left[rt] - 1] if left[rt] > 0 else 0, post[right[rt] + 1] if right[rt] < self.idx else 0))\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        left = {}\n",
    "        right = {}\n",
    "        dic = {}\n",
    "        self.idx = - 1 \n",
    "        def dfs(node, d):\n",
    "            if not node:\n",
    "                return \n",
    "            self.idx += 1 \n",
    "            left[node.val] = self.idx \n",
    "            dic[self.idx] = d\n",
    "            dfs(node.left, d + 1)\n",
    "            dfs(node.right, d + 1)\n",
    "            right[node.val] = self.idx\n",
    "        dfs(root, 0)\n",
    "        pre = [0] * (self.idx + 1)\n",
    "        post = [0] * (self.idx + 1)\n",
    "        for i in range(self.idx + 1):\n",
    "            pre[i] = max(pre[i - 1] if i > 0 else 0, dic[i])\n",
    "            post[self.idx + 1 - 1 - i] = max(post[self.idx + 1 - 1 - i + 1] if i > 0 else 0, dic[self.idx + 1 - 1 - i])\n",
    "        # print(pre)\n",
    "        # print(post)\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            res.append(max(pre[left[q] - 1] if left[q] > 0 else 0, post[right[q] + 1] if right[q] < self.idx else 0))\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "        left = {}\n",
    "        right = {}\n",
    "        depth = {}\n",
    "        self.idx = - 1 \n",
    "        def dfs(node, d):\n",
    "            if not node:\n",
    "                return \n",
    "            self.idx += 1 \n",
    "            left[node.val] = self.idx \n",
    "            depth[self.idx] = d \n",
    "            dfs(node.left, d + 1)\n",
    "            dfs(node.right, d + 1)\n",
    "            right[node.val] = self.idx \n",
    "        \n",
    "        dfs(root, 0)\n",
    "        n = len(depth)\n",
    "        pre = [0] * (self.idx + 1)\n",
    "        post = [0] * (self.idx + 1)\n",
    "        for i in range(self.idx + 1):\n",
    "            pre[i] = max(pre[i - 1] if i > 0 else 0, depth[i])\n",
    "            post[n - i - 1] = max(post[n - i] if i > 0 else 0, depth[n - i - 1])\n",
    "        \n",
    "        res = []\n",
    "        for rt in queries:\n",
    "            res.append(max(pre[left[rt] - 1] if left[rt] > 0 else 0, post[right[rt] + 1] if right[rt] < self.idx else 0))\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DfsEulerOrder:\n",
    "    def __init__(self, dct, root=0):\n",
    "        # 模板：dfs序与欧拉序，支持在线区间修改树上边，并且实时查询任意两点树上距离\n",
    "        n = len(dct)\n",
    "        for i in range(n):\n",
    "            dct[i].sort(reverse=True)  # 按照子节点编号从小到大进行遍历\n",
    "        self.start = [-1] * n  # 每个原始节点的dfs序号开始点也是node_to_order\n",
    "        self.end = [-1] * n  # 每个原始节点的dfs序号结束点\n",
    "        self.parent = [-1] * n  # 每个原始节点的父节点\n",
    "        self.order_to_node = [-1] * n  # 每个dfs序号对应的原始节点编号\n",
    "        self.node_depth = [0] * n  # 每个原始节点的深度\n",
    "        self.order_depth = [0] * n  # 每个dfs序号的深度\n",
    "        self.euler_order = []  # 每个dfs序回溯得到的欧拉序号的原始节点编号\n",
    "        self.euler_in = [-1] * n  # 每个原始节点再欧拉序中首次出现的位置\n",
    "        self.euler_out = [-1] * n  # 每个原始节点再欧拉序中最后出现的位置\n",
    "        self.build(dct, root)\n",
    "        return\n",
    "\n",
    "    def build(self, dct, root):\n",
    "        # 生成dfs序与欧拉序相关信息\n",
    "        order = 0\n",
    "        stack = [[root, -1]]\n",
    "        while stack:\n",
    "            i, fa = stack.pop()\n",
    "            if i >= 0:\n",
    "                self.euler_order.append(i)\n",
    "                self.start[i] = order\n",
    "                self.order_to_node[order] = i\n",
    "                self.end[i] = order\n",
    "                self.order_depth[order] = self.node_depth[i]\n",
    "                order += 1\n",
    "                stack.append([~i, fa])\n",
    "                for j in dct[i]:\n",
    "                    if j != fa:  # 注意访问顺序可以进行调整，比如字典序正序逆序\n",
    "                        self.parent[j] = i\n",
    "                        self.node_depth[j] = self.node_depth[i] + 1\n",
    "                        \n",
    "                        stack.append([j, i])\n",
    "            else:\n",
    "                i = ~i\n",
    "                if i != root:\n",
    "                    self.euler_order.append(self.parent[i])\n",
    "                if self.parent[i] != -1:\n",
    "                    self.end[self.parent[i]] = self.end[i]\n",
    "        for i, num in enumerate(self.euler_order):\n",
    "            self.euler_out[num] = i  # 计算欧拉序的位置\n",
    "            if self.euler_in[num] == -1:\n",
    "                self.euler_in[num] = i\n",
    "        return\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n",
    "\n",
    "        dct = defaultdict(list)\n",
    "        n = 0\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal n\n",
    "            if not node:\n",
    "                return\n",
    "            x = node.val - 1\n",
    "            if x + 1 > n:\n",
    "                n = x + 1\n",
    "            if node.left:\n",
    "                dct[x].append(node.left.val - 1)\n",
    "                dfs(node.left)\n",
    "            if node.right:\n",
    "                dct[x].append(node.right.val - 1)\n",
    "                dfs(node.right)\n",
    "            return\n",
    "\n",
    "        dfs(root)\n",
    "        edge = [dct[i] for i in range(n)]\n",
    "        r = root.val - 1\n",
    "        dfs_order = DfsEulerOrder(edge, r)\n",
    "        pre = list(accumulate(dfs_order.order_depth, max, initial=0))\n",
    "        post = list(accumulate(dfs_order.order_depth[::-1], max))[::-1] + [0]\n",
    "\n",
    "        ans = []\n",
    "        for i in queries:\n",
    "            i -= 1\n",
    "            s, e = dfs_order.start[i], dfs_order.end[i]\n",
    "            a = pre[s]\n",
    "            b = post[e + 1]\n",
    "            ans.append(a if a > b else b)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
